1. Field of the Invention
The present invention relates to a process for controlling or managing the circulation of messages of a same size in an array of elementary processors organized according to a parallel structure such as a structure of the SIMD type (Single Instruction Stream Multiple Data Stream). It also relates to an interconnection system for performing this process.
The invention has applications in the field of data processing. It more specifically applies to the processing of data relative to medium level pixels and to graphic generation.
2. Description of the Related Art
Among systems permitting the processing of data, there are many which do not ensure a consistency of the messages transmitted between different processors of the same array. Very frequently, when a processor supplies on the network a message having several data, the data are mixed, on reception by the receiving processor with respect to the message, with other data from messages supplied by other processors. The receiving processor must then carry out a sorting operation on the data received in order to reconstitute the messages.
During the use of massively parallel machines of the SIMD type, it is known to use as a basis regular exchanges between the processors in order to avoid such data mixing.
In the case of an application to the processing of images, these SIMD-type, massively parallel machines can ensure certain image processing levels. Thus, it is considered that the processing operations with respect to images can be classified in three levels, namely:
a low level consisting of a processing of the image from sensors in order to deduce a filtered image therefrom; PA1 a medium level consisting of extracting from the filtered image symbols useful in the sequence of processing by a data transformation from an iconic format to a symbolic format; PA1 a high level consisting of processing these symbols and then transforming them in order to deduce therefrom the actions to be performed, said level containing the intelligence of the image processing because it in particular contains the decision taking and shape recognition algorithms. PA1 wherein in that a question of priorities of interconnection modules for transmission and for reception of messages is established by the circulation of tokens in the network and in that one size of messages to be transmitted on the network is specified prior to the first transmission, the process comprising: PA1 if the memory space is inadequate, the interconnection module returns the message to the network, PA1 if the memory space is adequate, the interconnection module stores the first data item of the message and then all the successive data items until it detects an end of the message; PA1 if at least one message has been stored, the interconnection module supplies the first data item of the stored message to the network and then all the successive data items of the stored message; PA1 if no message has been stored, the interconnection module waits until it receives a following token. PA1 a plurality of elementary processors able to perform asynchronous processing operations, organized in accordance with a parallel structure and communicating with one another in a synchronous manner; and PA1 a plurality of interconnection modules, each interconnection module being associated with an elementary processor in order to ensure the connection of said elementary processor to the network, PA1 a cell connected to the cells of adjacent processors and ensuring, when a token is present, on the one hand the reception of the first data item of the message circulating in the network and intended for the elementary processor with which it is associated, and on the other hand, the transmission of the message which the processor wishes to send to the network; PA1 a reception module connected between the cell and the elementary processor and ensuring the storage of complete messages received by the cell and intended for the elementary processor; PA1 a transmission module connected between the elementary processor and the cell and ensuring the storage of complete messages which the elementary processor wishes to send to the network.
High level processing operations are most frequently carried out by multiprocessor systems of the MIMD type (Multiple Instruction Stream Multiple Data Stream), i.e. complex structures permitting a parallelism of both the instructions and the data.
The low level processing operations are generally carried out by multiprocessor systems of the SIMD type, i.e. systems in which the processors perform at the same time the same operation on the different data.
The medium level processing operations can also be performed by a SIMD multiprocessor system. Such a system is connected to a communications network or interconnection system ensuring numerous exchange types between the different processors of the system. It more particularly ensures the intercommunication of each processor to any random other processor, the communication from one processor to all the other processors, and the communication of all the processors to a single processor. Thus, it ensures a data distribution making it possible to effectively manage the available resources, namely the elementary processors of the system. In the medium level image processing operation, each processor can be associated with one pixel of an image or picture, or with a group of pixels, and can have access to adjacent pixels by means of interconnection links of the system. According to this system, the processors are organized in a parallel structure and all processors wishing to carry out a processing operation perform the same processing operation at the same time. Such an interconnection system is described in French patent application 2,680,026.
These massively parallel systems are generally used on square, rectangular, hexagonal or hypercube mesh networks and only such network classes provide a sufficiently simple electronics system to implement architectures with a high degree of parallelism. However, on such networks, the inter-processor links are static and scarcely permit irregular communications between the processors as a result of the synchronism of their operation. Moreover, in order to retain a simple management of these interconnection systems, the efficiency of the network is frequently satisfied in order to obtain data consistency.